package q142

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	//使用快慢指针(弗洛伊德的兔子)
	if head==nil{
		return nil
	}
	if head.Next==nil{
		return nil
	}

	var f=head.Next.Next //快指针
	var s=head.Next //慢指针

	for f!=s{
		if f==nil{
			return nil
		}

		s=s.Next
		if f.Next==nil{
			return nil
		}
		f=f.Next.Next
	}

	//上述运行后肯定是有环,将慢指针移至头部
	s=head
	for s!=f{
		s=s.Next
		f=f.Next
	}

	return f
}
